﻿Imports System.Collections.ObjectModel

''' <summary>
''' Represents the structure of an DFA that manage serveral states and edges
''' </summary>
Public Class DFAModel
    Private m_nfa As NFAModel
    Private m_states As List(Of DFAState)

    Private Sub New()
        m_states = New List(Of DFAState)
    End Sub

    Public ReadOnly Property States() As ReadOnlyCollection(Of DFAState)
        Get
            Return m_states.AsReadOnly()
        End Get
    End Property

    Private m_alphabet As HashSet(Of Object)

    Private Sub AddState(ByVal state As DFAState)
        m_states.Add(state)
        state.Index = m_states.Count - 1

        'check accept stats
        Dim nfaState = m_nfa.States
        Dim acceptStateTokens = (From i In state.NFAStateSet Where nfaState(i).IsAcceptState Order By nfaState(i).Priority Select nfaState(i).TokenTypeIndex).ToArray
        If acceptStateTokens.Length > 0 Then
            state.TokenTypeIndex = acceptStateTokens(0)
        End If

    End Sub

    Private Shared Function BuildTransitionTable(ByVal state As DFAState) As CharIndexTable(Of Integer)
        Dim edges = From edge In state.OutEdges Order By edge.Priority Select edge

        Dim transitionTable As New CharIndexTable(Of Integer)
        For Each edge In edges
            Dim condition = edge.GetConditionValue

            If TypeOf condition Is Char Then
                transitionTable.Add(DirectCast(condition, Char), edge.TargetState.Index)
            Else
                transitionTable.Add(DirectCast(condition, CharRange), edge.TargetState.Index)
            End If
        Next

        Return transitionTable
    End Function

    ''' <summary>
    ''' Test the DFA model. Determin if the DFA accept a particular string
    ''' </summary>
    ''' <param name="inputString">The string used to test DFA</param>
    ''' <returns>A token index of the token type if the DFA stopped at an accept state. 0 means no token type.</returns>
    ''' <remarks>
    ''' The performance of this method is low. It's designed only to test or debug your DFA model.
    ''' </remarks>
    Public Function SimulateRun(ByVal inputString As String) As Integer
        If inputString Is Nothing Then Return Nothing
        Dim engine = GenerateScannerEngine()

        For i = 0 To inputString.Length - 1
            engine.Input(inputString(i))
        Next

        Return engine.GetCurrentTokenTypeIndex
    End Function

    Public Function GenerateScannerEngine() As DFAScannerEngine
        If m_states Is Nothing OrElse m_states.Count = 0 Then
            Throw New InvalidOperationException("The DFA model is invalid. There's no state in this DFA model")
        End If

        Dim stateCount = m_states.Count

        'build transiton table and accept state table
        Dim transitionTable(0 To stateCount - 1) As CharIndexTable(Of Integer)
        Dim acceptStateTable(0 To stateCount - 1) As Integer

        For i = 0 To stateCount - 1
            Dim state = m_states(i)

            Dim stateTransition = BuildTransitionTable(state)
            transitionTable(i) = stateTransition
            acceptStateTable(i) = state.TokenTypeIndex
        Next

        Return New DFAScannerEngine(transitionTable, acceptStateTable)
    End Function

    ''' <summary>
    ''' Compresses the DFA model to reduce the amount of states.
    ''' </summary>
    ''' <remarks>
    ''' After compression, the debug information of DFA model will lost. 
    ''' Compression will also cost some time.
    ''' </remarks>
    Public Sub Compress()
        '1 combine duplicated edges
        For Each state In m_states
            Dim edges = state.OutEdges

            Dim charEdges = (From e In edges Where Not e.IsCharRangeCondition Select e).ToArray
            Dim rangeEdges = (From e In edges Where e.IsCharRangeCondition
                             Order By DirectCast(e.GetConditionValue(), CharRange).Length
                             Select e).ToArray

            For Each charEdge In charEdges
                For Each rangeEdge In rangeEdges
                    If charEdge.TargetState Is rangeEdge.TargetState AndAlso
                        AreConditionsMatch(charEdge.GetConditionValue(), rangeEdge.GetConditionValue()) Then
                        state.RemoveEdge(charEdge)
                    End If
                Next
            Next

            If rangeEdges.Length <= 1 Then Continue For

            For i = 0 To rangeEdges.Length - 1
                For j = i + 1 To rangeEdges.Length - 1
                    If rangeEdges(i).TargetState Is rangeEdges(j).TargetState AndAlso
                        AreConditionsMatch(rangeEdges(i).GetConditionValue(), rangeEdges(j).GetConditionValue()) Then
                        state.RemoveEdge(rangeEdges(i))
                    End If
                Next
            Next
        Next

        '2 get minimum DFA
    End Sub

    Public Shared Function FromNFA(ByVal nfa As NFAModel) As DFAModel
        Dim dfa As New DFAModel
        dfa.m_nfa = nfa
        Dim nfaStates = nfa.States()

        'get alphabet - the condition char set
        dfa.m_alphabet = New HashSet(Of Object)
        For Each s In nfaStates
            For Each edge In s.OutEdges
                If Not edge.IsEmptyCondition Then dfa.m_alphabet.Add(edge.GetConditionValue())
            Next
        Next

        'state0 is an empty state
        Dim state0 As New DFAState()

        dfa.AddState(state0)

        'state1 is closure (nfa_s[0])
        Dim pre_state1 As New DFAState
        Dim nfaStartIndex = nfa.EntryEdge.TargetState.Index
        Debug.Assert(nfaStartIndex >= 0)
        pre_state1.NFAStateSet.Add(nfaStartIndex)

        Dim state1 = GetClosure(nfa, pre_state1)
        dfa.AddState(state1)

        'begin algorithm
        Dim p = 1, j = 0
        Do While j <= p
            For Each condition In dfa.m_alphabet
                Dim edgePriority As Integer
                Dim e = GetDFAState(nfa, dfa.m_states(j), condition, edgePriority)

                Dim isSetExist As Boolean = False
                For i = 0 To p
                    If e.NFAStateSet.SetEquals(dfa.m_states(i).NFAStateSet) Then
                        Dim newEdge As New DFAEdge(condition, dfa.m_states(i))
                        newEdge.Priority = edgePriority
                        dfa.m_states(j).AddEdge(newEdge)

                        isSetExist = True
                    End If
                Next

                If Not isSetExist Then
                    p += 1
                    dfa.AddState(e)

                    Dim newEdge As New DFAEdge(condition, e)
                    newEdge.Priority = edgePriority
                    dfa.m_states(j).AddEdge(newEdge)
                End If
            Next

            j += 1
        Loop

        Return dfa
    End Function

    Private Shared Function GetClosure(ByVal nfa As NFAModel, ByVal state As DFAState) As DFAState
        Dim closure As New DFAState

        Dim nfaStates = nfa.States()

        closure.NFAStateSet.UnionWith(state.NFAStateSet)
        Dim changed As Boolean = True

        Do While changed
            changed = False

            Dim lastStateSet = closure.NFAStateSet.ToList()
            For Each stateIndex In lastStateSet
                Dim nfaState = nfaStates(stateIndex)
                For Each edge In nfaState.OutEdges
                    If edge.IsEmptyCondition Then
                        Dim target = edge.TargetState

                        'check if in set
                        Dim targetIndex = target.Index
                        Debug.Assert(targetIndex >= 0)
                        changed = closure.NFAStateSet.Add(targetIndex) OrElse changed
                    End If
                Next
            Next
        Loop

        Return closure
    End Function

    Private Shared Function GetDFAState(ByVal nfa As NFAModel, ByVal start As DFAState, ByVal condition As Object, ByRef edgePriority As Integer) As DFAState
        Dim target As New DFAState
        Dim nfaStates = nfa.States()
        Dim priorityList As New List(Of Integer)

        For Each nfaStateIndex In start.NFAStateSet
            Dim nfaState = nfaStates(nfaStateIndex)

            For Each edge In nfaState.OutEdges
                If AreConditionsMatch(condition, edge.GetConditionValue) Then

                    Dim targetIndex = edge.TargetState.Index
                    Debug.Assert(targetIndex >= 0)
                    target.NFAStateSet.Add(targetIndex)

                    priorityList.Add(edge.Priority)
                End If
            Next
        Next

        'get the highest priority as the DFA edge's priority
        If priorityList.Count > 0 Then edgePriority = priorityList.Min() Else edgePriority = 0

        Return GetClosure(nfa, target)
    End Function

    Private Shared Function AreConditionsMatch(ByVal condition1 As Object, ByVal condition2 As Object) As Boolean
        If TypeOf condition1 Is Char AndAlso TypeOf condition2 Is Char Then
            Return condition1.Equals(condition2)
        ElseIf TypeOf condition1 Is Char AndAlso TypeOf condition2 Is CharRange Then
            Return DirectCast(condition2, CharRange).Contains(DirectCast(condition1, Char))
        ElseIf TypeOf condition1 Is CharRange AndAlso TypeOf condition2 Is CharRange Then
            Return DirectCast(condition1, CharRange).IsSubRangeOf(DirectCast(condition2, CharRange))
        End If

        Return False
    End Function

End Class
